What We're Building 🎯
- La Estructura de Datos: A Cola de Prioridad (CP).
- Es un tipo de dato abstracto como una lista o cola, pero con una particularidad.
- Cada elemento tiene una "prioridad" (una clave).
- Cuando haces "pop," siempre obtienes el elemento con la mayor prioridad.siempre get the item with the highest priority.
- Las Operaciones:
- 1.
push(k) - 2.
peek() - 3.
pop()
- 1.
- La Implementación: We'll use a Montículo Binario Máximo.
- ¿Por qué un montículo? It's efficient! A heap gives us:
push: O(log N)pop: O(log N)peek: O(1)
What is a Max-Heap?
A binary tree with two simple rules:
1. Propiedad de Forma
It's a árbol binario completo. Todos los niveles están llenos, excepto tal vez el último, que se llena de izquierda a derecha. No hay huecos.
Haz clic en una hoja para eliminarla
2. Propiedad de Montículo Máximo
A parent's key is mayor o igual que its children's keys. This guarantees the más grande element is always at the root.
Storing the Tree 💾
Because the tree is completo, podemos almacenarlo perfectamente en un arreglo simple.
Index Math (0-based)
For a node at index i:
- Padre
(i - 1) // 2 - Hijo Izquierdo
2 * i + 1 - Hijo Derecho
2 * i + 2
Consejo: Memorize these formulas! They are the key to navigating the "tree" inside your array.